package com.shm.leetcode;

/**
 * 198. 打家劫舍
 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 *
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 *
 *
 *
 * 示例 1：
 *
 * 输入：[1,2,3,1]
 * 输出：4
 * 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
 *      偷窃到的最高金额 = 1 + 3 = 4 。
 * 示例 2：
 *
 * 输入：[2,7,9,3,1]
 * 输出：12
 * 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
 *      偷窃到的最高金额 = 2 + 9 + 1 = 12 。
 *
 *
 * 提示：
 *
 * 0 <= nums.length <= 100
 * 0 <= nums[i] <= 400
 * @author SHM
 */
public class Rob {
    /**
     * 题意分析：题目只问最优值，并没有问最优解，因此可以考虑使用「动态规划」。
     *
     * 思路分析：「打家劫舍」是典型的 多阶段、有约束 的决策最优化问题，解决这一类问题有固定的思考模式。我们省略「自顶向下」的记忆化递归的方法，直接从「自底向上」的思路，介绍这一类问题的思考角度：以线性的方式一天一天递推求解。
     *
     * 如果我们直接将问题的问法定义成状态，会发现当前这个房子「偷」和「不偷」会影响到后面的房子「偷」与「不偷」，可以进行分类讨论。
     *
     * 一个更常见的做法是：只要有约束，就可以增加维度消除这种约束带来的影响，这样的做法确定了每一阶段具体做什么，可以简化分类讨论。把「状态」定义得清楚、准确，「状态转移方程」就更容易推导。
     *
     * 方法一：动态规划（定义二维状态数组）
     * 第 1 步：设计状态
     * 由于当前考虑的房屋有两种选择：「偷」和「不偷」。我们用 0 表示「不偷」，用 1 表示「偷」，即：
     *
     * dp[i][0] 表示：考虑区间 [0..i] ，并且下标为 i 的这个房间偷，能够偷窃到的最高金额；
     * dp[i][1] 表示：考虑区间 [0..i] ，并且下标为 i 的这个房间不偷，能够偷窃到的最高金额。
     * 注意：这里定义的状态 具有有前缀性质，即：当前的状态值综合考虑了之前所有的状态值。并且第二维固定了选择（偷与不偷），通过增加维度 消除了后效性，方便状态转移方程的推导。
     *
     * 友情提示：由于状态定义更细致，记录了更多的信息，为后面的决策找到了确切的参考依据。
     *
     * 第 2 步：状态转移方程
     * 「状态转移方程」可以理解为「不同阶段之间的联系」。「当前这一间房屋是否偷取」只和「左边这一间房屋是否偷取」的状态相关（从左向右计算，不考虑右边），进行分类讨论：
     *
     * 情况 1：下标为 i 的房屋不偷，有两种可能：① 左边房间不偷，② 左边房间偷。取二者最大值，即：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])；
     * 情况 2：下标为 i 的房屋偷：由于相邻的两个房间不能同时偷取，只有左边房间不偷，当前房间才可以偷，即：dp[i][1] = dp[i - 1][0] + nums[i]。
     * 第 3 步：考虑初始化
     * 第 11 天（下标为 00）是容易得到的：
     *
     * dp[0][0] = 0，这是由于第二维规定了不偷取，所以为 00；
     * dp[0][1] = nums[0]，这是由于第二维规定了偷取，所以为 nums[0]。
     * 第 4 步：考虑输出
     * 由于状态值的定义具有前缀性质，最后一天的状态值考虑了之前所有的天数的情况；
     * 下标为 len - 1 这个房屋可以偷，也可以不偷，取二者最大值。
     * 友情提示：希望通过这个问题的输出，大家能够体会到「动态规划」其实没有为一个问题设计专门的解决方案，它考虑了所有的可能的情况，计算出最优值，并且不记录最优的具体解是什么。
     *
     * 复杂度分析：
     *
     * 时间复杂度：O(N)O(N)，NN 是数组的长度；
     * 空间复杂度：O(N)O(N)，状态数组的大小为 2N2N，记为 O(N)O(N)。
     *
     * 作者：liweiwei1419
     * 链接：https://leetcode-cn.com/leetbook/read/learning-algorithms-with-leetcode/9wmq9r/
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        int n = nums.length;
        if(n==0){
            return 0;
        }
        int[][] dp = new int[n][2];
        dp[0][0]=0;
        dp[0][1]=nums[0];
        for(int i=1;i<n;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);
            dp[i][1]=dp[i-1][0]+nums[i];
        }

        return Math.max(dp[n-1][0],dp[n-1][1]);
    }

    /**
     * 下面我们稍微修改一下定义，可以避免设置初始值，此时需要将状态数组多设置一行。
     *      *
     *      * dp[i][0]：考虑区间 [0..i)，并且下标为 i - 1 的这个房屋不偷；
     *      * dp[i][1]：考虑区间 [0..i) ，并且下标为 i - 1 的这个房屋偷。
     *      * 状态转移从 i = 1 开始，具体表现在：
     *      *
     *      * 数组多使用一行；
     *      * 使用输入数组的下标的时候，需要考虑一格偏移。
     *      复杂度分析：
     *
     * 时间复杂度：O(N)O(N)，NN 是数组的长度；
     * 空间复杂度：O(N)O(N)，状态数组的大小为 2(N + 1)2(N+1)，记为 O(N)O(N)。
     *
     * 作者：liweiwei1419
     * 链接：https://leetcode-cn.com/leetbook/read/learning-algorithms-with-leetcode/9wmq9r/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * @param nums
     * @return
     */
    public int rob_2(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n+1][2];
//        dp[0][0]=0;
//        dp[0][1]=nums[0];
        for(int i=1;i<=n;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);
            dp[i][1]=dp[i-1][0]+nums[i-1];
        }

        return Math.max(dp[n][0],dp[n][1]);
    }

    /**
     * 第 5 步：考虑优化空间
     * 由于只关心最后一个状态值，并且当前行只参考了上一行的状态值，可以使用「滚动变量」完成。
     *
     * 注意：优化空间的代码丢失了一定可读性，也会给编码增加一点点难度，在很多情况下是没有必要的。如果读者对于优化空间的技巧不太熟悉，或者没有把握一下子写对的话，可以先写出不优化空间的代码，先把代码写对更重要。
     *
     * 参考代码 3：（基于参考代码 1 的空间优化代码）
     *
     *
     * 使用「滚动变量」技巧，将使用空间优化到常数级别。在编码的时候，需要注意，只要访问到 dp 数组的时候，需要对下标 % 2，等价的写法是 & 1。
     *
     * 复杂度分析：
     *
     * 时间复杂度：O(N)O(N)，NN 是数组的长度；
     * 空间复杂度：O(1)O(1)，状态数组的大小为 44，常数空间。
     * 作者：liweiwei1419
     * 链接：https://leetcode-cn.com/leetbook/read/learning-algorithms-with-leetcode/9wmq9r/
     * @param nums
     * @return
     */
    public int rob_3(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[2][2];
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i%2][0] = Math.max(dp[(i-1)%2][0],dp[(i-1)%2][1]);
            dp[i%2][1] = dp[(i-1)%2][0]+nums[i];
        }
        return Math.max(dp[(n-1)%2][0],dp[(n-1)%2][1]);
    }

    /**
     * 这个问题还可以不针对当前考虑的房间是否偷取多设计一维状态，下面展示了这种状态下状态转移的过程。
     *
     * 方法二：动态规划（使用一维状态数组）
     * 第 1 步：状态定义
     * dp[i] 表示：考虑偷取 [0..i] 区间的房间号，能够偷窃到的最高金额。
     *
     * 第 2 步：推导状态转移方程
     * 依然是，对于每一个房间，我们有偷和不偷两种选择。
     *
     * 如果当前房间不偷，上一个房间可以偷，用状态表示为 dp[i - 1]；
     * 如果当前房间偷，上一个房间一定不可以偷，用状态表示为 dp[i - 2] + nums[i]。
     * 得到状态转移方程：dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) 。
     *
     * 第 3 步：思考初始化
     * 根据状态转移方程，dp[i] 依赖 dp[i - 1] 和 dp[i - 2] ，因此 dp[0] 和 dp[1] 需要先计算出来，否则在状态转移的过程中，下标会越界。
     *
     * dp[0] = nums[0]，只有一个房间必须偷；
     * dp[1] = max(nums[0], nums[1])，两个房间不能同时偷，需要偷金额较大的那个房间。
     * 第 4 步：思考输出
     * 输出为 dp[len - 1]。状态的定义包括了 [0..len - 1] 整个区间的情况，因此最后一个状态就是输出值。
     *
     * 复杂度分析：
     *
     * 时间复杂度：O(N)O(N)，NN 是数组的长度；
     * 空间复杂度：O(N)O(N)，状态数组的大小为 NN。
     * 作者：liweiwei1419
     * 链接：https://leetcode-cn.com/leetbook/read/learning-algorithms-with-leetcode/9wmq9r/
     * @param nums
     * @return
     */
    public int rob_4(int[] nums) {
        int n = nums.length;
        if(n==0){
            return 0;
        }
        if(n==1){
            return nums[0];
        }
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for (int i = 2; i < n; i++) {
            // 分类讨论：在偷 nums[i] 与不偷 nums[i] 中选择一个最大值
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[n-1];
    }

    public int rob_6(int[] nums) {
        int n = nums.length;
        if(n==0){
            return 0;
        }
        if(n==1){
            return nums[0];
        }
        int a = nums[0],
        b = Math.max(nums[0],nums[1]);
        for (int i = 2; i < n; i++) {
            // 分类讨论：在偷 nums[i] 与不偷 nums[i] 中选择一个最大值
            int t = b;
            b = Math.max(t,a+nums[i]);
            a=t;
        }
        return b;
    }

    /**
     * 依然是状态可以多开一格，区别只是在初始化和递推的时候 i 的下标 dp 数组和输入数组 nums 之间有一个单位的偏移，请大家注意这里的细节。
     * 复杂度分析：
     *
     * 时间复杂度：O(N)O(N)，NN 是数组的长度；
     * 空间复杂度：O(N)O(N)，状态数组的大小为 N + 1N+1。
     * @param nums
     * @return
     */
    public int rob_5(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n+1];
        dp[0]=0;
        dp[1]=nums[0];
        for (int i = 2; i <= n; i++) {
            // 注意：nums 数组的下标选择有一个位置的偏移
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i-1]);
        }
        return dp[n];
    }
}
